package day190901;

import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/9/1 上午 10:19
 */
public class Contest {

    public int integerBreak(int n) {
        int[] dp = new int[5];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        dp[3] = 6;
        dp[4] = 9;
        if (n < 7) {
            return dp[n - 2];
        }
        int[] copyOf = Arrays.copyOf(dp, n);
        for (int i = 5; i < n; i++) {
            copyOf[i] = 3 * copyOf[i - 3];
        }
        return copyOf[n - 2];
    }

    public int integerBreak2(int n) {
        int[] memory = new int[n + 1];

        memory[2] = 1;
        for (int i = 3; i <= n; i++) {
            for ( int j = 1; j <= i - 1; j++) {
                memory[i] = Math.max(memory[i], Math.max(j * memory[i - j], j * (i - j)));
            }
        }
        return memory[n];
    }

    public static void main(String[] args) {
        Contest contest = new Contest();
        contest.integerBreak2(10);
    }

    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        int score = 0;
        for (int i = 0; i <= calories.length - k; i++) {
            int j = i;
            int calory = 0;
            int temp = k;
            while (temp > 0) {
                calory += calories[j];
                temp--;
                j++;
                if (j == calories.length) {
                    break;
                }
            }
            if (calory < lower) {
                score--;
            }
            if (calory > upper) {
                score++;
            }
        }
        return score;
    }

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> list = new ArrayList<>();
        int[][] count = new int[s.length() + 1][26];
        for (int i = 0; i < s.length(); i++) {
            count[i + 1] = count[i];
            count[i + 1][s.charAt(i) - 'a']++;
        }
        for (int[] query : queries) {
            int left = query[0];
            int right = query[1];
            int k = query[2];
            int[] L = count[left];
            int[] R = count[right + 1];
            int modify = 0;
            for (int i = 0; i < 26; i++) {
                if (Math.abs(R[i] - L[i]) % 2 != 0) {
                    modify++;
                }
            }
            if (modify - 2 * k > 1) {
                list.add(Boolean.FALSE);
            } else {
                list.add(Boolean.TRUE);
            }
        }
        return list;
    }

    public List<Boolean> canMakePaliQueries2(String s, int[][] queries) {
        int n = s.length();
        int[][] count = new int[n][26];

        count[0][s.charAt(0) - 'a']++;
        for (int i = 1; i < n; ++i) {
            count[i][s.charAt(i) - 'a']++;
            for (int j = 0; j < 26; ++j) {
                count[i][j] += count[i - 1][j];
            }
        }

        List<Boolean> res = new ArrayList<>();
        for (int[] query : queries) {
            int left = query[0], right = query[1], k = query[2];
            if (k >= right - left + 1) {
                res.add(true);
                continue;
            }
            int modify = 0;
            for (int i = 0; i < 26; ++i) {
                int p = left == 0 ? count[right][i] : count[right][i] - count[left - 1][i];
                if (p > 0) {
                    if (p % 2 == 1) {
                        modify++;
                    }
                }
            }
            if ((modify / 2 <= k) || modify == 0 || (modify == 1 && k == 0)) {
                res.add(true);
            } else {
                res.add(false);
            }
        }
        return res;
    }

    private boolean checkIsPali(String substring) {
        StringBuilder builder = new StringBuilder(substring);
        return builder.reverse().toString().equals(substring);
    }

    public int numPrimeArrangements(int n) {
        long ret = 1;
        int num = 0;
        for (int i = 1; i <= n; i++) {
            if (isPrime(i)) {
                num++;
            }
        }
        for (int i = 1; i <= num; i++) {
            ret = ret * i % 1000000007;
        }
        for (int i = 1; i <= n - num; i++) {
            ret = ret * i % 1000000007;
        }
        return Math.toIntExact(ret);
    }

    private boolean isPrime(int x) {
        if (x == 1) {
            return false;
        }
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> answer = new ArrayList<>();
        int[] ans = new int[puzzles.length + 1];
        Map<Integer, Integer> bitMap = new HashMap<>(16);
        for (String word : words) {
            int k = 0;
            for (int i = 0; i < word.length(); i++) {
                k |= (1 << (word.charAt(i) - 'a'));
            }
            if (bitMap.containsKey(k)) {
                Integer value = bitMap.get(k);
                bitMap.put(k, value++);
            } else {
                bitMap.put(k, 0);
            }
        }
        for (int i = 0; i < puzzles.length; i++) {
            String puzzle = puzzles[i];
            int k = 0;
            for (int j = 0; j < puzzle.length(); j++) {
                k |= (1 << (puzzle.charAt(j) - 'a'));
            }
            for (int j = k; j != 0; j = (j - 1) & k) {
                if (((1 << (puzzle.charAt(0) - 'a')) & j) != 0) {
                    ans[i] += (bitMap.get(j) == null ? 0 : bitMap.get(j));
                }
            }
        }
        for (int an : ans) {
            answer.add(an);
        }
        return answer;
    }

}
